package src.CodeTop;

/**
 * 旋转链表
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 *
 *  
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[4,5,1,2,3]
 * 示例 2：
 *
 *
 * 输入：head = [0,1,2], k = 4
 * 输出：[2,0,1]
 *
 */

public class _61RotateList {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        ListNode head = TestListNode.generateLinkedList(5, arr);
        ListNode target = rotateRight(head, 2);
        TestListNode.showLinkedList(target);
    }

    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0)
            return head;
        // 定义链表长度
        int length = 1;
        // 遍历指针
        ListNode cur = head;
        // 遍历计算链表长度并把遍历指针移动到尾结点
        while (cur.next != null) {
            cur = cur.next;
            length++;
        }
        // 将最后一个结点连接到头结点，成环
        cur.next = head;
        // 要考虑k远大于链表长度的情况
        // k为此时的尾指针应该移动的距离
        k %= length;
        k = length - k;
        // 尾指针位移到真正的需要断裂的位置
        for (int i = 0 ; i < k ; i++) {
            cur = cur.next;
        }
        // 标记新链表的头结点
        head = cur.next;
        // 将当前结点的下一个结点置空
        cur.next = null;
        return head;
    }
}
